package com.azure.code.graph.bipartite;

import java.util.LinkedList;
import java.util.Queue;

/***
 * 二分图：
 *   如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，
 *   一个来自 B 集合，就将这个图称为 二分图 。
 * 图的双色问题：
 *   给你一幅图，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？
 *   ----> 双色问题 等同于二分图的判断问题
 *
 * 实际案例：
 *  如何存储电影演员和电影之间的关系？
 *  如果使用哈希存储，需要两个哈希表分别存储【每个演员到电影列表】的映射和【每部电影到演员列表】的映射
 *  如果用【图】结构存储，将电影和参演的演员连接，很自然地就成为一幅二分图
 *  每个电影节点的相邻节点就是参演改电影的所有演员，每个演员的相邻的节点就是该演员参演过的所有电影
 *  <p>二分图的遍历框架</p>
 *  <code>
 *      // 图遍历框架
 *      void traverse(Graph graph,boolean[] visited, int v){
 *          visited[v] =true;
 *          // 遍历节点 v 的所有相邻节点 neighbor
 *          for( int neighbor : graph.neighbors(v)){
 *              if(!visited[neighbor]) {
 *                  // 相邻节点 neighbor 没有被访问过
 *                  // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
 *                  traverse(graph,visited,neighbor);
 *              } else {
 *                  // 相邻节点 neighbor 已经被访问过
 *                  // 那么应该比较节点 neighbor 和 节点 v 的颜色
 *                  // 如果相同，则此图不是二分图
 *              }
 *          }
 *      }
 *  </code>
 */
public class BipartiteGraph_785 {
    // 记录图是否符合二分图
    boolean ok = true;
    // 记录图中节点的颜色 , false 和 true 代表两种不同的颜色
    private boolean[] color;
    private boolean[] visited;

    // 主函数，输入邻接表，判断是否是二分图
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color = new boolean[n];
        visited = new boolean[n];
        // 因为图不一定是联通的，可能存在多个子图
        // 所有要把每个节点都作为起点进行一次遍历
        // 如果发现任何一个子图不是二分图，则整幅图都不算二分图
        for (int v = 0; v < n; v++) {
            if (!visited[v]) {
                dfs(graph, v);
            }
        }
        return ok;
    }

    private void dfs(int[][] graph, int v) {
        // 如果已经不是二分图了，就不用让费时间再递归遍历
        if (!ok) return;

        visited[v] = true;
        for (int w : graph[v]) {
            if (!visited[w]) {
                // 相邻节点 w 没有被访问过
                // 那么应该给节点 w 涂上节点 v 不同的颜色
                color[w] = !color[v];
                // 继续遍历 w
                dfs(graph, w);
            } else {
                // 相邻节点 w 已经被访问过
                // 根据 v 和 w 的颜色判断是否二分图
                if (color[w] == color[v]) {
                    // 若相同，则此图不是二分图
                    ok = false;
                }
            }
        }
    }

    // 从start 节点开始进行 bfs 遍历
    private void bfs(int[][] graph, int start) {
        Queue<Integer> queue = new LinkedList<>();
        visited[start] = true;
        queue.offer(start);
        while (!queue.isEmpty() && ok) {
            int v = queue.poll();
            // 从节点 v  向所有的相邻节点扩散
            for (int w : graph[v]) {
                if(!visited[w]){
                    // 相邻节点 w 没有被访问过
                    // 那么应该给节点 w 涂上和节点 v 不同的颜色
                    color[w] = !color[v];
                    // 标记 w 节点，并放入队列中
                    visited[w] = true;
                    queue.offer(w);
                }else {
                    // 相邻节点 w 已经被访问过
                    // 根据 v 和 w 的颜色判断是否是二分图
                    if(color[w] == color[v]){
                        // 若相同，则此图不是二分图
                        ok = false;
                    }
                }
            }
        }
    }
}
